package org.example.algorithm.trie;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 */
public class WordDictionarySolution {
    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("ab");
        Boolean res = wordDictionary.search("..");
        System.out.println(res);
    }

}

class WordDictionary {
    private WordDictionary[] children;
    private Boolean isEnd;

    public WordDictionary() {
        this.children = new WordDictionary[26];
        this.isEnd = false;
    }

    public void addWord(String word) {
        WordDictionary node = this;
        for (int i=0;i<word.length();i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new WordDictionary();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return searchNode(this, word, 0);
    }

    public boolean searchNode(WordDictionary node, String word, int start) {
        if (word.isEmpty() && node.isEnd) {
            return true;
        }
        if (word.isEmpty()) {
            return false;
        }
        for (int i=start;i<word.length();i++) {
            if (word.charAt(i) == '.') {
                return searchNodeChildren(node, word, i+1);
            }
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEnd;
    }

    private boolean searchNodeChildren(WordDictionary node, String word, int start) {
        for (int i=0; i<node.children.length; i++) {
            if (node.children[i] != null && searchNode(node.children[i], word, start)) {
                return true;
            }
        }
        return false;
    }
}
